-
1 travelling salesman problem
задача о коммивояжере
задача о бродячем торговце
Вид задачи математического программирования, состоит в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. В обобщенной форме задача формулируется как определение на сети такого пути, связывающего два или более узлов, который минимизирует (или максимизирует) некоторый критерий оптимальности, представляющий собой функцию (как правило, сумму) известных характеристик ребер этой сети. На допустимые маршруты могут быть наложены ограничения: например, запрет возвращения к уже пройденному узлу. З.о к. — одна из типичных задач, решаемых методом динамического программирования. О сложности ее говорит такой факт: если рассматриваются четыре города (точки), то число возможных маршрутов равно 6, а уже при 11 городах существует более 3,5 млн. допустимых маршрутов. В общем случае, когда число городов n, количество маршрутов равно (n-1)!, т.е. «(n-1) факториал». Задача, следовательно, заключается в поиске сокращенных способов расчета, позволяющих отказаться от сплошного перебора возможных маршрутов. Такие способы есть. Они основаны на использовании сетевых и матричных моделей. Алгоритмы, позволяющие решать на компьютерах З.о к., используются не только для выбора оптимальных маршрутов автотранспорта при кольцевой доставке товаров (например, в торговую сеть), но и при решении таких задач, которые на первый взгляд никакого отношения к З.о.к. не имеют, например, в планировании производства на конвейерах, выпускающих машины различных моделей. С помощью таких алгоритмов рассчитывают оптимальные партии, позволяющие выпускать заданный объем продукции с минимумом затрат на переналадку конвейера.
[ http://slovar-lopatnikov.ru/]Тематики
Синонимы
EN
Англо-русский словарь нормативно-технической терминологии > travelling salesman problem
-
2 travelling salesman problem
иссл. опер. = traveling salesman problemАнгло-русский экономический словарь > travelling salesman problem
-
3 travelling salesman problem
Математика: задача коммивояжёра, задача о коммивояжёреУниверсальный англо-русский словарь > travelling salesman problem
-
4 travelling-salesman problem
Вычислительная техника: задача коммивояжёраУниверсальный англо-русский словарь > travelling-salesman problem
-
5 travelling salesman problem
English-Russian dictionary of logistics > travelling salesman problem
-
6 travelling salesman problem
English-Russian scientific dictionary > travelling salesman problem
-
7 travelling-salesman problem
English-Russian information technology > travelling-salesman problem
-
8 traveling salesman problem
иссл. опер. задача коммивояжера, задача о коммивояжере, задача о бродячем торговце (задача, заключающаяся в отыскании наилучшего маршрута для коммивояжера, который должен объехать все порученные города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд)Syn:Англо-русский экономический словарь > traveling salesman problem
-
9 problem
1) задача; проблема3) трудность, затруднение•- boundary value problem - card matching problem - central limit problem - decision problem under risk - decision problem under uncertainty - extremum problem - fair division problem - gambling problem - gasoline blending problem - incompletely structured problem - optimal path problem - optimal stopping problem - portfolio selection problem - precisely specified problem - recursively solvable problem - sequential decision programming problem - sequential occupancy problem - shortest path problem - shortest route problem - standard control problem - three houses and three wells problem -
10 traveling salesman
-
11 field salesman
-
12 TSP
1) Общая лексика: hum. сокр. Truncated Signal Peptide, тройной суперфосфат2) Компьютерная техника: Tapi Service Provider, Team Software Processes, Temporary Storage Program, telecommunications service priority3) Авиация: экранированная витая пара4) Американизм: Tiny Suspended Particles, Transition Stakeholders Panel5) Спорт: The Supporter Page6) Военный термин: Tactical Sensor Planner, Threat Support Package, Training Support Base, Training Support Package, Troop Structure Program, tactical strike program, technical specifications, technical support package, telemetry simulation program, temporary standard practice, test site position, test status panel, test support package, test support program, transit servicing park, transshipment point, tri-service program, trial-shot point7) Техника: Titanium Sublimation Pump, temperature-sensitive period, test software program, thermally stimulated polarization, thermally stimulated process, time at source point, time sorting program, time-shared program, tube support plate8) Шутливое выражение: The Smelly People, Try Some Phosphorus9) Химия: Tri Sodium Phosphate10) Математика: Travelling Salesman Problem11) Автомобильный термин: throttle solenoid positioner (Ford), Система стабилизации прицепа: (Trailer Stability Program)12) Ветеринария: Team Sick Puppy13) Политика: Terrorist State of Pakistan14) Телекоммуникации: провайдер телекоммуникационных услуг, Telecom Service Provider15) Сокращение: Target Signal Processor, Teleprocessing Services Program, Thrift Savings Plan, Time & Space Processing Inc. (USA), Time Synchronization Protocol, Tracking Signal Processor, Turret Stabilised Platform16) Физиология: Thoracic spine, teaspoon (5 mL), thrombospondin17) Электроника: Temperature- Sensitive Parameter18) Вычислительная техника: traveling salesman problem, Texture and Shading Processor (IC, Graphik)20) Иммунология: T cell-specific serine proteinase, transferred solid phase21) Геофизика: вертикальное время22) Транспорт: Traveler Service Point23) Пищевая промышленность: Texturized Soy Protein24) Фирменный знак: Texas Screw Products25) Экология: total suspended particulates26) СМИ: The Softback Preview27) Деловая лексика: Totally Superior Product, Transactional Services Provider28) Сетевые технологии: Tunnel Setup Protocol, telecommunication service priority, категория услуг при предоставлении связи29) Полимеры: trisodium phosphate30) Программирование: командный процесс разработки программного обеспечения (см. team software process)31) Акустика: параметры Тиля/Смолла (Thielle & Small parameters)32) Отопление: ( trisodium phosphate) тринатрийфосфат33) Химическое оружие: total suspended particulate34) Расширение файла: Telephony Service Provider35) Нефть и газ: долото TSP, термостойкое поликристаллическое алмазное долото TSP36) Туннелестроение: (tunnel seismic prediction) прогноз сейсмичности тоннеля37) Агрохимия: triple superphosphate38) Единицы измерений: Ten Square Pounds -
13 tsp
1) Общая лексика: hum. сокр. Truncated Signal Peptide, тройной суперфосфат2) Компьютерная техника: Tapi Service Provider, Team Software Processes, Temporary Storage Program, telecommunications service priority3) Авиация: экранированная витая пара4) Американизм: Tiny Suspended Particles, Transition Stakeholders Panel5) Спорт: The Supporter Page6) Военный термин: Tactical Sensor Planner, Threat Support Package, Training Support Base, Training Support Package, Troop Structure Program, tactical strike program, technical specifications, technical support package, telemetry simulation program, temporary standard practice, test site position, test status panel, test support package, test support program, transit servicing park, transshipment point, tri-service program, trial-shot point7) Техника: Titanium Sublimation Pump, temperature-sensitive period, test software program, thermally stimulated polarization, thermally stimulated process, time at source point, time sorting program, time-shared program, tube support plate8) Шутливое выражение: The Smelly People, Try Some Phosphorus9) Химия: Tri Sodium Phosphate10) Математика: Travelling Salesman Problem11) Автомобильный термин: throttle solenoid positioner (Ford), Система стабилизации прицепа: (Trailer Stability Program)12) Ветеринария: Team Sick Puppy13) Политика: Terrorist State of Pakistan14) Телекоммуникации: провайдер телекоммуникационных услуг, Telecom Service Provider15) Сокращение: Target Signal Processor, Teleprocessing Services Program, Thrift Savings Plan, Time & Space Processing Inc. (USA), Time Synchronization Protocol, Tracking Signal Processor, Turret Stabilised Platform16) Физиология: Thoracic spine, teaspoon (5 mL), thrombospondin17) Электроника: Temperature- Sensitive Parameter18) Вычислительная техника: traveling salesman problem, Texture and Shading Processor (IC, Graphik)20) Иммунология: T cell-specific serine proteinase, transferred solid phase21) Геофизика: вертикальное время22) Транспорт: Traveler Service Point23) Пищевая промышленность: Texturized Soy Protein24) Фирменный знак: Texas Screw Products25) Экология: total suspended particulates26) СМИ: The Softback Preview27) Деловая лексика: Totally Superior Product, Transactional Services Provider28) Сетевые технологии: Tunnel Setup Protocol, telecommunication service priority, категория услуг при предоставлении связи29) Полимеры: trisodium phosphate30) Программирование: командный процесс разработки программного обеспечения (см. team software process)31) Акустика: параметры Тиля/Смолла (Thielle & Small parameters)32) Отопление: ( trisodium phosphate) тринатрийфосфат33) Химическое оружие: total suspended particulate34) Расширение файла: Telephony Service Provider35) Нефть и газ: долото TSP, термостойкое поликристаллическое алмазное долото TSP36) Туннелестроение: (tunnel seismic prediction) прогноз сейсмичности тоннеля37) Агрохимия: triple superphosphate38) Единицы измерений: Ten Square Pounds -
14 network analysis
1) сетевой анализ, анализ сетейа) иссл. опер., т. граф. (группа пространственно-аналитических операций, имеющих целью исследование свойств линейных пространственных объектов, образующих сети, напр., гидрографические сети, сети коммуникаций и т. п.; анализ основан на формализмах и алгоритмах теории графов и обычно включает поиск наикратчайшего пути между узлами линейной сети, расчет маршрута движения с минимальными издержками, решение задачи размещения ресурсов и т. п.)See:б) упр. (метод планирования сложных проектов и контроля за их выполнением, основанный на графическом представлении последовательности операций и расчете критического пути)See:project network analysis, program evaluation and review technique, critical path, critical path analysis2) эк., соц. сетевой подход [анализ\], теория сетей (подход в к изучению отдельного рынка или всего хозяйства с учетом существующих социальных взаимоотношений между отдельными людьми или организациями; методологически близок структурной социологии)Syn:See:social network, formal network, informal network, network embeddedness, network properties, network ties, strong ties, weak ties, structural hole, structural similarity, bounded solidarity, Baker, Wayne E.* * * -
15 TSP
travelling salesman problem задача коммивояжера в математическом программировании ———————— time-shared program выч. программа, работающая в режиме разделения времени -
16 TSP
выч. программа, работающая в режиме разделения времени задача коммивояжера в математическом программировании
См. также в других словарях:
Travelling Salesman Problem — [ trævəlɪȖ seɪlzmən prɔbləm, englisch], Problem des Handelsreisenden, Rundfahrtproblem, Operations Research: kombinatorisches Optimierungsproblem, bei dem durch eine vorgegebene Menge von Orten von einem bestimmten Ausgangsort aus der kürzeste… … Universal-Lexikon
Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… … Wikipedia
Travelling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
Travelling Salesman Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein … Deutsch Wikipedia
travelling salesman problem — noun The problem in combinatorial optimization in which, given a number of cities and the costs of travelling from one to the other, it is required to determine the cheapest route that visits each city once and then returns to the initial city … Wiktionary
Travelling salesman (disambiguation) — A travelling salesman is a travelling vendor of goods.Travelling salesman may also refer to:* Traveling Saleseman (film), a 1921 comedy film * Traveling Salesmen ( The Office episode), the twelfth episode of the third season of the US version of… … Wikipedia
Bottleneck traveling salesman problem — The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization. It is stated as follows: Find the Hamiltonian cycle in a weighted graph with the minimal weight of the most weighty edge of the… … Wikipedia
Function problem — In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.Notable examples include the travelling salesman problem, which asks for the … Wikipedia
P versus NP problem — Unsolved problems in computer science Is P = NP ? … Wikipedia
Job-shop problem — The job shop problem (JSP) is a problem in discrete or combinatorial optimization, and is a generalization of the famous travelling salesman problem. It is a prominent illustration of a class of problems in computational complexity theory which… … Wikipedia
P = NP problem — The relationship between the complexity classes P and NP is an unsolved question in theoretical computer science. It is considered to be the most important problem in the field – the Clay Mathematics Institute has offered a $1 million US prize… … Wikipedia